package main

import (
	"fmt"
	"sort"
	"strconv"
)

//将两个数字拼接起来，确保可以生成较小值，依次排序
//内建函数排序:8ms 16%,3MB 20%
func minNumber(nums []int) string {
	sort.Slice(nums, func(i, j int) bool {
		x := fmt.Sprintf("%d%d", nums[i], nums[j])
		y := fmt.Sprintf("%d%d", nums[j], nums[i])
		return x < y
	})
	var ans string
	for _, n := range nums {
		ans += fmt.Sprintf("%d", n)
	}
	return ans
}

//冒泡排序：24ms 1%, 5.5MB 5%
func minNumber1(nums []int) string {
	for i := 0; i < len(nums)-1; i++ {
		for j := 0; j < len(nums)-i-1; j++ {
			x := fmt.Sprintf("%d%d", nums[j], nums[j+1])
			y := fmt.Sprintf("%d%d", nums[j+1], nums[j])
			if x > y {
				nums[j], nums[j+1] = nums[j+1], nums[j]
			}
		}
	}
	res := ""
	for _, v := range nums {
		res += fmt.Sprintf("%d", v)
	}
	return res
}

//快速排序
func minNumber2(nums []int) string {
	quickSort(nums, 0, len(nums)-1)
	res := ""
	for i := 0; i < len(nums); i++ {
		res += fmt.Sprintf("%d", nums[i])
	}
	return res
}
func quickSort(nums []int, start, end int) {
	if start >= end {
		return
	}
	p := nums[start]
	i, j := start, end
	for i < j {
		for i < j && compair(nums[j], p) {
			j--
		}
		nums[i] = nums[j]
		for i < j && compair(p, nums[i]) {
			i++
		}
		nums[j] = nums[i]
	}
	nums[i] = p
	quickSort(nums, start, i-1)
	quickSort(nums, i+1, end)
}
func compair(a, b int) bool {
	stra, strb := strconv.Itoa(a), strconv.Itoa(b)
	if stra+strb >= strb+stra {
		return true
	} else {
		return false
	}
}

func main() {
	fmt.Println(minNumber([]int{12, 435, 7786, 3, 7}))
	fmt.Println(minNumber1([]int{12, 435, 7786, 3, 7}))
	fmt.Println(minNumber2([]int{12, 435, 7786, 3, 7}))
}
